package com.hdu.other.dp.maxSubArraySum;

public class lc2560 {
    class Solution {
        public int minCapability(int[] nums, int k) {
            int l = Integer.MAX_VALUE;
            int r = Integer.MIN_VALUE;
            for (int num : nums)
            {
                l = Math.min(l, num);
                r = Math.max(r, num);
            }

            int ans = 0;
            while (l <= r)
            {
                int capacity = l + ((r - l) >> 1);
                if (f(nums, capacity) >= k)
                {
                    ans = capacity;
                    r = capacity - 1;
                }
                else
                {
                    l = capacity + 1;
                }
            }
            return ans;
        }

        int f(int[] nums, int capacity)
        {
            int len = nums.length;
            if (len == 1)
            {
                return capacity >= nums[0] ? 1 : 0;
            }
            if (len == 2)
            {
                return Math.min(nums[0], nums[1]) <= capacity ? 1 : 0;
            }

            int a = capacity >= nums[0] ? 1 : 0;
            int b = Math.min(nums[0], nums[1]) <= capacity ? 1 : 0;

            for (int i = 2; i < len; i++)
            {
                int cur = Math.max(
                        b,
                        a + (capacity >= nums[i] ? 1 : 0)
                );
                a = b;
                b = cur;
            }
            return b;
        }
    }
}
